package com.google.codejam.qua2013.Lawnmower;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class Lawnmower {

    public static void main(String[] args) {
        String inputFile = args[0];
        String outputFile = args[1];
        readAndSolve(inputFile, outputFile);
    }

    public static String readAndSolve(String inFileName, String outFileName) {
        File file = new File(inFileName);
        BufferedReader bufferedReader = null;
        try {
            bufferedReader = new BufferedReader(new FileReader(file));
            FileWriter fileWriter = new FileWriter(outFileName, true);
            String readLine = null;
            int testCase = 0;
            int currentTestCaseIndex = 1;
            int line = 0;
            // intialize array
            String[][] board = new String[4][];
            for (int i = 0; i < 4; i++) {
                board[i] = new String[4];
            }
            boolean isSquareLine = false;
            boolean isDataLine = false;
            int dataLineNumber = 0;
            int N = 0;
            int M = 0;
            ArrayList<SquareUnit> squares = new ArrayList<SquareUnit>();
            SquareUnit[][] IndexUnitMap = null;

            while ((readLine = bufferedReader.readLine()) != null) {
                if (readLine.trim().length() <= 0) {
                    continue;
                }
                if (line == 0) {
                    testCase = Integer.parseInt(readLine);
                    isSquareLine = true;
                } else if (isSquareLine) {
                    String[] squareDescription = readLine.split(" ");
                    N = Integer.parseInt(squareDescription[0]);
                    M = Integer.parseInt(squareDescription[1]);
                    IndexUnitMap = new SquareUnit[N][M];
                    isDataLine = true;
                    isSquareLine = false;
                    squares.clear();
                } else if (isDataLine) {
                    dataLineNumber++;
                    String[] columnValues = readLine.split(" ");
                    
                    for (int i = 0; i < M; i++) {
                        SquareUnit unit = new SquareUnit(dataLineNumber - 1, i, Integer.parseInt(columnValues[i]),
                                                         false);
                        IndexUnitMap[dataLineNumber - 1][i] = unit;
                        squares.add(unit);
                    }
                    if (dataLineNumber == N) {
                        fileWriter.append("Case #" + currentTestCaseIndex + ": ");
                        // solve the problem
                        sortByLengthAsc(squares);
                        boolean isPossible = true;
                        for (int i = 0; i < squares.size(); i++) {
                            SquareUnit checkUnit = squares.get(i);
                            if (checkUnit.mark) {
                                continue;
                            }
                            if (!isPossible(checkUnit, IndexUnitMap, N, M)) {
                                isPossible = false;
                                break;
                            }
                            checkUnit.mark = true;
                        }
                        if (isPossible) {
                            fileWriter.append("YES");
                        } else {
                            fileWriter.append("NO");
                        }
                        fileWriter.append("\n");
                        // mark status
                        currentTestCaseIndex++;
                        isSquareLine = true;
                        isDataLine = false;
                        dataLineNumber = 0;
                        squares.clear();
                    }
                }
                line++;
            }
            fileWriter.flush();
            fileWriter.close();
            bufferedReader.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }

    public static void sortByLengthAsc(ArrayList<SquareUnit> squarelist) {
        Comparator comp = new MyComparator();
        Collections.sort(squarelist, comp);
    }

    public static boolean isPossible(SquareUnit checkUnit, SquareUnit[][] indexMap, int RowNumber, int ColumnNumber) {
        boolean isRowPossible = true;
        // check row
        for (int i = 0; i < ColumnNumber; i++) {
            // itself
            if (checkUnit.indexM == i) {
                continue;
            }
            SquareUnit unit = indexMap[checkUnit.indexN][i];
            if (unit.mark) {
                continue;
            }
            if (unit.grassLenght > checkUnit.grassLenght) {
                isRowPossible = false;
                break;
            }
            unit.mark = true;
        }
        if (isRowPossible) {
            return true;
        }
        // check column
        boolean isColumnPossible = true;
        for (int i = 0; i < RowNumber; i++) {
            // itself
            if (checkUnit.indexN == i) {
                continue;
            }
            SquareUnit unit = indexMap[i][checkUnit.indexM];
            if (unit.mark) {
                continue;
            }
            if (unit.grassLenght > checkUnit.grassLenght) {
                isColumnPossible = false;
                break;
            }
            unit.mark = true;
        }
        return isColumnPossible;
    }
//    public static void printlist(ArrayList<SquareUnit> list){
//        for(int i=0; i < list.size(); i++){
//            SquareUnit unit = list.get(i);
//            System.out.println(unit.indexN+","+unit.indexM+","+unit.grassLenght);
//        }
//        System.out.println();
//    }
//    public static void printArray(String[] list){
//        for(String item: list){
//            System.out.print(item+" ");
//        }
//        System.out.println();
//    }

}
